Network devices and data networks that process and communicate data traffic often implement multiple paths across which data traffic may be communicated In certain applications multiple paths, such as multiple paths between a single source and single destination, may be grouped together (e.g., as a logical trunk or an aggregation group). In such applications, the network devices (nodes) communicating network data traffic (e.g., data packets) may use load balancing techniques to distribute the data traffic across the links included in an aggregation group. One such technique is the use of hash-based load balancing.
To perform such hash-based load balancing across a set of aggregates, a common approach is to hash a set of packet fields to resolve which among a set of possible route choices to select (e.g., which member of an aggregate). At every hop in the network, each node may have more than one possible next-hop/link that will lead to the same destination. For purposes of this disclosure, a node may be viewed as any level of granularity in a data network. For instance a node could be an incoming data port, a combination of the incoming data port and an aggregation group, a network device, a packet switch, or may be some other level of granularity.
In a network or network device, each node would select a next-hop/link based on a hash of a set of packet fields which do not change for the duration of a flow. A flow may be defined by a number of different parameters, such as source and destination addresses (e.g., IP addresses or MAC addresses), TCP flow parameters, or any set of parameters that are common to a given set of data traffic. Using such an approach, packets within a flow, or set of flows that produce the same hash value, will follow the same path at every hop. This approach leads to poor distribution of multiple flows to aggregate members and causes starvation of nodes, particularly in large multi-hop, multi-path networks (e.g., certain nodes in a multi-hop network may not receive any data traffic), especially as you move further away from the node (called root node) at which the traffic entered the network.